import "babel-polyfill";
import type from "../../type";
import {islice} from "../../algorithm/array";
import {enumerate, map, chain, repeat, slice} from "../../algorithm/iterator";
import {ZeroDivisionError} from "../error";
import {fastExponentation} from "../generic-algorithm";

const {min} = Math;

export var valueOf = Symbol("Polynomial.valueOf");

export var PolynomialBase = class {
    _create(array) {
        var polynomial = new this.constructor();
        polynomial._coeff = array;
        return polynomial;
    };

    get [Symbol.toStringTag]() {
        return "Polynomial";
    }

    get degree() {
        return this._coeff.length ? this._coeff.length - 1 : -Infinity;
    }

    *[Symbol.iterator](direction = 1) {
        if (direction > 0) {
            yield* this._coeff;
        } else {
            for (let i = this._coeff.length - 1; --i >= 0;) {
                yield this._coeff[i];
            }
        }
    }

    monic() {
        if (this._coeff.length) {
            return this.divide(this, this._coeff[this._coeff.length - 1]);
        } else {
            return this;
        }
    }

    shr(p, shift) {
        if (shift === 0) {
            return p;
        } else {
            return new this.constructor(...p._coeff::islice(shift));
        }
    }

    divide(p1, p2) {
        return this.divmod(p1, p2)[0];
    }

    pow(base, exponent, modulus) {
        base = this.from(base);
        if (modulus === undefined) {
            return fastExponentation(base, exponent, {
                multiply: this::this.multiply,
                square: this::this.square,
                one: this.constructor.one
            });
        } else {
            modulus = this.from(modulus);
            return fastExponentation(this.mod(base, modulus), exponent, {
                multiply: (m, n) => this.mod(this.multiply(m, n), modulus),
                square: n => this.mod(this.square(n), modulus),
                one: this.constructor.one
            });
        }
    }
};

export default function(Type, BaseType = PolynomialBase) {
    var trim = function() {
        while (this.length && Type.isZero(this[this.length - 1])) {
            this.pop();
        }
        return this;
    };

    var Polynomial = class extends PolynomialBase {
        constructor(p) {
            super();
            if (arguments.length) {
                if (p instanceof Polynomial) {
                    this._coeff = p._coeff;
                } else if (p instanceof PolynomialBase) {
                    this._coeff = p._coeff.map(Type)::trim();
                } else if (type(p) === "String") {
                    this._fromString(p, arguments.length === 1 ? "x" : arguments[1]);
                } else {
                    this._coeff = Array.prototype.map.call(arguments, Type)::trim();
                }
            } else {
                this._coeff = [];
            }
        }

        from(p) {
            return p instanceof this.constructor ? p : new this.constructor(p);
        }

        toString(symbol = "x") {
            var data = this._coeff;
            if (data.length === 0) {
                return "0";
            }
            var list = [];
            if (!Type.isZero(data[0])) {
                list.push(`${data[0]}`);
            }
            if (data.length > 1 && !Type.isZero(data[1])) {
                if (Type.isOne(data[1])) {
                    list.push(symbol);
                } else {
                    list.push(`${data[1]}*${symbol}`);
                }
            }
            for (let i = 2, length = data.length; i < length; ++i) {
                if (!Type.isZero(data[i])) {
                    if (Type.isOne(data[i])) {
                        list.push(`${symbol}^${i}`);
                    } else {
                        list.push(`${data[i]}*${symbol}^${i}`);
                    }
                }
            }
            return list.join(" + ");
        }

        [valueOf](value) {
            value = Type(value);
            return this._coeff.reduceRight((x, y) => Type.add(Type.multiply(x, value), y), Type.zero);
        }

        get leadingCoeff() {
            return this._coeff.length ? this._coeff[this._coeff.length - 1] : Type.zero;
        }

        get(degree) {
            return degree >= this._coeff.length ? Type.zero : this._coeff[degree];
        }
        set(mapping) {
            var result = this._coeff.slice();
            for (let degree in mapping) {
                if (mapping.hasOwnProperty(degree)) {
                    degree = parseInt(degree);
                    if (degree >= result.length) {
                        result = result.concat(
                            new Array(degree - result.length).fill(Type.zero),
                            [Type(mapping[degree])]
                        );
                    } else {
                        result[degree] = mapping[degree];
                    }
                }
            }
            return this._create(result);
        }

        eq(p1, p2) {
            var data1 = this.from(p1)._coeff;
            var data2 = this.from(p2)._coeff;
            if (data1.length !== data2.length) {
                return false;
            }
            var length = data1.length;
            for (let i = 0; i < length; ++i) {
                if (!Type.eq(data1[i], data2[i])) {
                    return false;
                }
            }
            return true;
        }

        shl(p, shift) {
            if (shift === 0) {
                return p;
            } else {
                return this._create(new Array(shift).fill(Type.zero).concat(p._coeff));
            }
        }

        add(p1, p2) {
            var data1 = this.from(p1)._coeff;
            var data2 = this.from(p2)._coeff;
            if (data1.length > data2.length) {
                [data1, data2] = [data2, data1];
            }
            var result = [];
            var l1 = data1.length;
            for (let i = 0; i < l1; ++i) {
                result.push(Type.add(data1[i], data2[i]));
            }
            Array.prototype.push.apply(result, data2.slice(l1));
            return this._create(result::trim());
        }
        subtract(p1, p2) {
            var data1 = this.from(p1)._coeff;
            var data2 = this.from(p2)._coeff;
            var l1 = data1.length;
            var l2 = data2.length;
            var result = [];
            for (let i = 0, min_length = min(l1, l2); i < min_length; ++i) {
                result.push(Type.subtract(data1[i], data2[i]));
            }
            if (l1 > l2) {
                Array.prototype.push.apply(result, data1.slice(l2));
            } else if (l1 < l2) {
                result.push(...data2::islice(l1)::map(Type.negate));
            }
            return this._create(result::trim());
        }

        multiply(p1, p2) {
            var data1 = this.from(p1)._coeff;
            var data2 = this.from(p2)._coeff;
            if (data1.length === 0 || data2.length === 0) {
                return this.constructor.zero;
            }
            if (data1.length > data2.length) {
                [data1, data2] = [data2, data1];
            }
            var l1 = data1.length;
            var l2 = data2.length;
            if (l1 === 1) {
                if (Type.isOne(data1[0])) {
                    return this._create(data2);
                } else {
                    return this._create(data2.map(x => Type.multiply(x, data1[0]))::trim());
                }
            }
            var result = new Array(l1 + l2 - 1).fill(Type.zero);
            for (let i = 0; i < l1; ++i) {
                for (let j = 0; j < l2; ++j) {
                    result[i + j] = Type.add(result[i + j], Type.multiply(data1[i], data2[j]));
                }
            }
            return this._create(result::trim());
        }
        square(p) {
            var data = this.from(p)._coeff;
            var length = data.length;
            if (data.length === 0) {
                return this.constructor.zero;
            }
            var result = [Type.square(data[0])];
            for (let i = 1; i < length; ++i) {
                result.push(Type.zero, Type.square(data[i]));
                for (let j = 0; j < i; ++j) {
                    result[i + j] = Type.add(result[i + j], Type.multiply(Type.multiply(data[i], data[j]), 2));
                }
            }
            return this._create(result::trim());
        }

        divmod(p1, p2) {
            p1 = this.from(p1);
            var data1 = p1._coeff;
            var data2 = new this.constructor(p2)._coeff;
            var l2 = data2.length;
            if (l2 === 0) {
                p1 = `${p1}`;
                if (p1.includes(" ")) {
                    p1 = `(${p1})`;
                }
                throw new ZeroDivisionError(`${p1} / 0`);
            } else if (data1.length === 0 || (l2 === 1 && Type.isOne(data2[0]))) {
                return [p1, this.constructor.zero];
            } else if (data1.length < l2) {
                return [this.constructor.zero, p1];
            } else if (l2 === 1) {
                let divisor = data2[0];
                return [this._create(data1.map(x => Type.divide(x, divisor))), this.constructor.zero];
            }

            data1 = data1.slice();
            var offset = data1.length - l2;
            var inverse = Type.inverse(data2[l2 - 1]);
            var quotient = new Array(offset + 1).fill(Type.zero);
            while (offset >= 0) {
                let factor = Type.multiply(data1[data1.length - 1], inverse);
                quotient[offset] = factor;
                for (let i = 0; i < l2; ++i) {
                    data1[i + offset] = Type.subtract(data1[i + offset], Type.multiply(data2[i], factor));
                }
                offset = data1::trim().length - l2;
            }
            return [this._create(quotient), this._create(data1)];
        }
        mod(p1, p2) {
            p1 = this.from(p1);
            var data1 = p1._coeff;
            var data2 = this.from(p2)._coeff;
            var l2 = data2.length;
            if (l2 === 0) {
                p1 = `${p1}`;
                if (p1.includes(" ")) {
                    p1 = `(${p1})`;
                }
                throw new ZeroDivisionError(`(${p1}) / 0`);
            } else if (data1.length === 0 || l2 === 1) {
                return this.constructor.zero;
            } else if (data1.length < l2) {
                return p1;
            }

            data1 = data1.slice();
            var offset = data1.length - l2;
            var inverse = Type.inverse(data2[l2 - 1]);
            while (offset >= 0) {
                let factor = Type.multiply(data1[data1.length - 1], inverse);
                for (let i = 0; i < l2; ++i) {
                    data1[i + offset] = Type.subtract(data1[i + offset], Type.multiply(data2[i], factor));
                }
                offset = data1::trim().length - l2;
            } while (--offset >= 0);
            return this._create(data1);
        }

        deriv() {
            return new this.constructor(...this::enumerate()::slice(1)::map(
                ([degree, coeff]) => Type.multiply(degree, coeff)
            ));
        }
    };

    Polynomial.zero = new Polynomial();
    Polynomial.one = new Polynomial(1);
    Polynomial.instance = new Polynomial();

    return Polynomial;
};
